package com.dq.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/15  18:55
 * @Description:
 * 剑指 Offer 48. 最长不含重复字符的子字符串
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 */
public class NoDoubleCharSubString {
    public static void main(String[] args) {
        Solution solution = new NoDoubleCharSubString().new Solution();
        String s = "abba";
        System.out.println(solution.lengthOfLongestSubstring(s));
        System.out.println(Integer.MAX_VALUE);
    }
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> dic = new HashMap<>();
            int i = -1, res = 0;
            for(int j = 0; j < s.length(); j++) {
                if(dic.containsKey(s.charAt(j)))
                    i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
                dic.put(s.charAt(j), j); // 哈希表记录
                res = Math.max(res, j - i); // 更新结果
            }
            return res;
        }
        public int lengthOfLongestSubstring2(String s) {
            Map<Character, Boolean> win = new HashMap<>();
            int left = 0, right = 0;
            int ans = 0;
            while(right < s.length()){
                char ch = s.charAt(right);
                Boolean val = win.get(ch);
                if(val == null ) win.put(ch, true);
                else{
                    while(left<right && s.charAt(left)!=ch){
                        win.put(s.charAt(left++), null);
                    }
                    left++;
                }
                int t = right - left + 1;
                ans = ans > t ? ans : t;
                right++;
            }
            return ans;
        }
    }
}
